/*
 * @Author: szx
 * @Date: 2021-11-30 14:41:23
 * @LastEditTime: 2022-02-27 15:06:00
 * @Description:
 * @FilePath: \leetcode\1-99\28\28.js
 */
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
// var strStr = function (haystack, needle) {
//     const n = needle.length;
//     if (n == 0) return 0;

//     const m = haystack.length;
//     if (m < n) return -1;
//     for (let i = 0; i < m - n + 1; i++) {
//         let s = haystack.substr(i, n);
//         if (s == needle) return i;
//     }
//     return -1;
// };

var strStr = function (haystack, needle) {
    const n = haystack.length,
        m = needle.length;
    if (m === 0) {
        return 0;
    }

    // 创建pi也就是next数组，默认初始化都为0，里面的值表示第n个，下标从1开始
    const pi = new Array(m).fill(0);

    for (let i = 1, k = 0; i < m; i++) {
        // 往前找，找到匹配的。
        while (k > 0 && needle[i] !== needle[k]) {
            k = pi[k - 1];
        }
        if (needle[i] == needle[k]) {
            k++;
        }
        console.log(i, k);
        pi[i] = k;
    }
    console.log(pi);
    for (let i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = pi[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j === m) {
            return i - m + 1;
        }
    }
    return -1;
};
console.log(strStr('hellohell', 'llodlloc'));
